package org.hot100_1;

public class leetcode74 {
//    public int jump(int[] nums) {
//
//        if ( nums.length==1 ){
//            return 0;
//        }
//
//        int count = 0;
//        //下次跳转的最大范围
//        int nextRange = 0;
//        //当前跳转的最大范围
//        int currRange = 0;
//
//        for (int i = 0; i < nums.length; i++) {
//            nextRange=Math.max(nextRange,i+nums[i]);
//
//            if (nextRange>=nums.length-1){
//                count++;
//                break;
//            }
//
//            if (i==currRange){
//                count++;
//                currRange=nextRange;
//            }
//        }
//
//
//        return count;
//    }

    public int jump(int[] nums) {

        if (nums.length==1){
            return 0;
        }
        int count = 0;
        int currRange = 0;
        int nextRange = 0;

        for (int i =0; i < nums.length; i++) {
            nextRange=Math.max(nextRange,i+nums[i]);

            if (nextRange>=nums.length-1){
                return ++count;
            }

            if (i==currRange){
                currRange=nextRange;
                count++;
            }
        }


        return count;
    }
}
